Link List
Q1.
Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?Q2.
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,the reversed linked list should look like Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?Q3.
A doubly linked list is declared as: struct Node { int Value; struct Node *Fwd; struct Node *Bwd; };Where Fwd and Bwd represent forward and backward link to the adjacent elements of the list. Which of the following segment of code deletes the node pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last node of the list?Q4.
Consider the following ANSI C program:#include < stdio.h > #include < stdlib.h > struct Node{ int value; struct Node *next;}; int main( ) { struct Node *boxE, *head, *boxN; int index=0; boxE=head= (struct Node *) malloc(sizeof(struct Node)); head -> value = index; for (index =1; index < = 3; index++){ boxN = (struct Node *) malloc (sizeof(struct Node)); boxE -> next = boxN; boxN -> value = index; boxE = boxN; } for (index=0; index < = 3; index++) { printf("Value at index %d is %d\n", index, head -> value); head = head -> next; printf("Value at index %d is %d\n", index+1, head -> value); } } Which one of the following statements below is correct about the program?Q5.
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?Q6.
In a doubly linked list the number of pointers affected for an insertion operation will beQ7.
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?Q8.
Given two statementsInsertion of an element should be done at the last node of the circular listDeletion of an element should be done at the last node of the circular listQ9.
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: \Theta(N) \; delete , O(logN) \; insert , O(logN) \; find , and \Theta(N) \; decrease-key. What is the time complexity of all these operations put together?Q10.
The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef struct node { int value; struct node *next; } Node; Node *move_to_front(Node *head) { Node *p, *q; if ((head = = NULL: || (head->next = = NULL)) return head; q = NULL; p = head; while (p-> next !=NULL) { q=P; p=p->next; } _______________________________ return head; } Choose the correct alternative to replace the blank line.